package 堆;

import 动态数组.线性表.ArrayList;
import 动态链表.LinkedList;

import java.util.Iterator;

/**
 * 最大堆
 */
public class MaxHeap<E extends Comparable<E>> implements Iterable<E> {

    private ArrayList<E> data;

    public MaxHeap(){
        data = new ArrayList<>();
    }

    private int parent(int index){
        //底层使用数组来存储最大堆，角标大于0才有父节点
        if (index <= 0){
            throw new IllegalArgumentException("index out of range!");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index){
        return 2 * index + 1;
    }

    private int rightChild(int index){
        return 2 * index + 2;
    }

    public int size(){
        return data.size();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    public void clear(){
        data.clear();
    }

    public void add(E e){
        data.add(e);
        siftUp(data.size() - 1);
    }

    private void siftUp(int k) {
        //只要有父节点，并且比父节点的值大就交换顺序
        while (k > 0 && data.get(k).compareTo(data.get(parent(k))) > 0){
            //交换顺序和k的角标，并一直比较下去
            data.swap(k,parent(k));
            k = parent(k);
        }
    }

    public E findMax(){
        if (isEmpty()){
            return null;
        }
        return data.get(0);
    }

    public E findMin(){
        if (isEmpty()){
            return null;
        }
        E min = data.get(0);
        for (int i = 0; i < data.size(); i++) {
            if (data.get(i).compareTo(min) < 0)
                min = data.get(i);
        }
        return min;
    }

    public E extractMax(){
        E max = findMax();
        data.swap(0, data.size() - 1);
        data.remove(data.size() - 1);
        siftDown(0);
        return max;
    }

    private void siftDown(int k) {
        while (leftChild(k) < size()){
            int j = leftChild(k);
            if (rightChild(k) < size() && data.get(rightChild(k)).compareTo(data.get(k)) > 0){
                j = rightChild(k);
            }
            if (data.get(k).compareTo(data.get(j)) < 0){
                data.swap(k,j);
                k = j;
            }else {
                break;
            }
        }
    }

    public E replace(E e){
        E ret = findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }

    @Override
    public String toString() {
        ArrayList<String> list =  new ArrayList<>();
        list.add(data.get(0) + "" + "\n");
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()){
            int cur = queue.poll();
            int left = leftChild(cur);
            int right = rightChild(cur);
            StringBuilder sb = new StringBuilder();
            if (left < data.size()){
                sb.append(data.get(left) + " ");
                queue.offer(left);
            }
            if (right < data.size()){
                sb.append(data.get(right));
                queue.offer(right);
            }else if (left < data.size()){
                sb.append("null");
            }
            if (sb.length() != 0){
                list.add(sb.toString());
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(list.get(0));
        int index =1;
        for (int i = 1; i < list.size(); i++) {
            sb.append(list.get(i));
            if (i == Math.pow(2,index) - 1){
                sb.append("\n");
                index++;
            }else {
                sb.append("  ");
            }
        }
        return sb.toString();
    }


    @Override
    public Iterator<E> iterator() {
        return null;
    }
}
